
//496.下一个更大元素I
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        //先将nums2中每个位置下一个更大元素记录下来
        //从右往左：存储下一个可能满足条件的位置
        int n1=nums1.size(),n2=nums2.size();
        stack<int> st;
        unordered_map<int,int> m;   //存储nums2中每一个位置的元素,方便nums1在nums2中的查找
        st.push(nums2[n2-1]);
        m[nums2[n2-1]]=n2-1;        

        vector<int> next(n2,-1);  
        for(int i=n2-2;i>=0;i--)
        {
            m[nums2[i]]=i;  
            while(!st.empty()&&st.top()<nums2[i]) st.pop();  //找满足条件的下一个位置

            if(!st.empty()) next[i]=st.top();
            st.push(nums2[i]);
        }

        vector<int> ans(n1);   
        for(int i=0;i<n1;i++)  
        {
            int index=m[nums1[i]];  //index是nums2中与nums1[i]相同的位置下标
            ans[i]=next[index];
        }
        return ans;
    }
};